The stability of low-rank matrix reconstruction with respect to noise isinvestigated in this paper. The $\ell_*$-constrained minimal singular value($\ell_*$-CMSV) of the measurement operator is shown to determine the recoveryperformance of nuclear norm minimization based algorithms. Compared with thestability results using the matrix restricted isometry constant, theperformance bounds established using $\ell_*$-CMSV are more concise, and theirderivations are less complex. Isotropic and subgaussian measurement operatorsare shown to have $\ell_*$-CMSVs bounded away from zero with high probability,as long as the number of measurements is relatively large. The $\ell_*$-CMSVfor correlated Gaussian operators are also analyzed and used to illustrate theadvantage of $\ell_*$-CMSV compared with the matrix restricted isometryconstant. We also provide a fixed point characterization of $\ell_*$-CMSV thatis potentially useful for its computation.
展开▼
